package solution.tree;

import lib.tree.BNode;

/**
 * Merge two binary search tree
 * 
 * @author <a href="www.sureinterview.com">SureInterview</a>
 * 
 */
public class MergeBST {

	// used by method 2, the header of the converted link list
	BNode linkStart;

	// used by method 2, the previous inorder node
	BNode prevInordNode;

	/**
	 * get the next node in ascending order.
	 * 
	 * @return next node
	 */
	private BNode getNextNode() {
		if (linkStart == null)
			return null;
		BNode nxtNode = linkStart;
		linkStart = linkStart.right;
		nxtNode.right = null;
		nxtNode.parent = null;
		return nxtNode;
	}

	/**
	 * convert a tree to link list. The output is indicated by the linkStart
	 * 
	 * @param root
	 *            the tree
	 */
	private void linearizeTreeRec(BNode root) {
		// 1. setup and precondition
		if (root == null)
			return;

		// save off the left and right node because they will be overwritten
		// later.
		BNode right = root.right;
		BNode left = root.left;

		// 2 need to generate the link from largest to smallest. In that way,
		// only one pointer is needed.
		// > check right first
		linearizeTreeRec(right);

		if (linkStart == null) {
			// first node (the largest)
			root.left = null;
			root.right = null;
			linkStart = root;
		} else {
			// generate the link from right to left
			root.left = null;
			root.right = linkStart;
			linkStart = root;
		}

		// > check left
		linearizeTreeRec(left);
	}

	/**
	 * merge two BST.
	 * 
	 * @param bst1
	 *            bst 1
	 * @param bst2
	 *            bst 2
	 * @return a merged BST.
	 */
	public BNode merge(BNode bst1, BNode bst2) {
		if (bst1 == null)
			return bst2;
		if (bst2 == null)
			return bst1;

		if (bst1.value > bst2.value) {
			BNode temp = bst2.right;
			bst2.right = null;
			bst1.left = merge(bst1.left, bst2);
			bst1 = merge(bst1, temp);
			return bst1;
		} else if (bst1.value < bst2.value) {
			BNode temp = bst2.left;
			bst2.left = null;
			bst1.right = merge(bst1.right, bst2);
			bst1 = merge(bst1, temp);
			return bst1;
		} else {
			bst1.left = merge(bst1.left, bst2.left);
			bst1.right = merge(bst1.right, bst2.right);

			// handle the node bst2
			bst2.left = null;
			bst2.right = bst1.right;
			bst1.right = bst2;
			return bst1;
		}
	}

	/**
	 * merge two BSTs.
	 * 
	 * @param bst1
	 * @param bst2
	 * @return a merged bst
	 */
	public BNode merge2(BNode bst1, BNode bst2) {
		if (bst1 == null)
			return bst2;
		if (bst2 == null)
			return bst1;

		linearizeTreeRec(bst2);

		prevInordNode = null;

		BNode node = peekNode();
		BNode root = bst1;
		while (root.left != null) {
			root = root.left;
		}

		if (node.value < root.value) {
			root.left = node;
			getNextNode();
		}

		merge2rec(bst1);

		if (peekNode() != null) {
			prevInordNode.right = peekNode();
		}

		return bst1;
	}

	public void merge2rec(BNode root) {
		if (root == null)
			return;

		merge2rec(root.left);

		if (prevInordNode == null) {
			prevInordNode = root;
		} else {
			for (;;) {
				BNode node = peekNode();
				if (node == null)
					return;
				if (node.value >= root.value) {
					break;
				}

				node = getNextNode();
				node.right = prevInordNode.right;
				prevInordNode.right = node;
				prevInordNode = node;
			}
		}
		prevInordNode = root;
		merge2rec(root.right);
	}

	private BNode peekNode() {
		return linkStart;
	}
}
